{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# Arbres de Décision" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "import numpy as np\n", "import pandas as pd\n", "import matplotlib.pyplot as plt" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Problème de Classification\n", "\n", "Supposons que l'on cherche à résoudre un problème de classification, c'est à dire qu'à partir d'une liste d'informations sur un objet, on chercher à en déterminier une caractéristique.\n", "\n", "En cours, on a vu un exemple où l'on cherchait à reconnaître des fruits.\n", "On avait quelques caractéristiques, comme la couleur, la présence d'un noyau et le diamètre, à partir desquels on cherchait à deviner quel fruit c'était." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Question.** Donnez un autre exemple de problème de classification." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Réponse :" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Arbres de Décision\n", "\n", "Les arbres de décision essaient de reproduire un raisonnement logique à propos des données.\n", "Pour reconnaître notre fruit, une démarche rationnelle serait de se poser des questions pour restreindre les possibilités : \n", "\n", "* est-ce qu'il est jaune ? \n", "* est-ce que son diamètre est plus grand que 5 ?\n", "\n", "et ce jusqu'à ce qu'on arrive à trouver notre réponse...\n", "\n", "### Impureté d'un Ensemble de Labels\n", "\n", "On a vu en cours qu'on pouvait choisir une question en utilisant le score Gini, qui mesure \"l'impureté\" d'un ensemble.\n", "\n", "Soit un ensemble $y$ dont les éléments prennent $K$ valeurs différentes $c_1, \\dots c_K$.\n", "Alors le score Gini de $y$ est :\n", "\n", "$$ Gini(y) = \\sum_{c_k} p_k (1 - p_k), $$\n", "\n", "où $p_k = \\frac{\\text{nombre d'éléments de } y \\text{ valant } c_k}{\\text{taille de } y}$ est la probabilité d'associer la bonne valeur à $s_i$ si on lui donne une valeur tirée uniformément au hasard dans $S$." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Par exemple, pour l'ensemble `y = [\"Pomme\", \"Pomme\", \"Banane\", \"Citron\", \"Cerise\"]`, le score Gini est :\n", "$$\n", "\\begin{align}\n", "Gini(y) & = p_{Pomme} (1 - p_{Pomme}) + p_{Banane} (1 - p_{Banane}) + p_{Citron} (1 - p_{Citron}) + p_{Cerise} (1 - p_{Cerise}) \\\\\n", "& = 2/5 \\times 3/5 + 1/5 \\times 4/5 + 1/5 \\times 4/5 + 1/5 \\times 4/5 \\\\\n", "& = 0.72\n", "\\end{align}\n", "$$" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "La fonction suivante permet de calculer le score Gini d'un ensemble :" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "def gini(S):\n", " \n", " g = 1\n", " counts = np.unique(S, return_counts=True)\n", " \n", " for i in range(len(counts[0])):\n", " g -= (counts[1][i] / len(S)) ** 2\n", " \n", " return g" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Question.** Vérifier la valeur Gini de l'ensemble `y = [\"Pomme\", \"Pomme\", \"Banane\", \"Citron\", \"Cerise\"]` ci-dessus à l'aide de la fonction `gini`." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "y = [\"Pomme\", \"Pomme\", \"Banane\", \"Citron\", \"Cerise\"]\n", "\n", "# calculer le score de y" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Question.** Quand est-ce que le score Gini d'un ensemble vaut $0$ ?" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Réponse :" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Application aux Arbres de Décision\n", "\n", "On a donc maintenant une métrique que nous permet de mesurer à quel point un ensemble est \"pur\", c'est à dire à quel point il est loin d'un ensemble où tous les éléments ont la même valeur.\n", "\n", "Ainsi, on peut évaluer la réponse à une question en utilisant cette mesure d'impureté.\n", "Supposons que l'on ait un ensemble $S$, et qu'on pose une question, par exemple \"est-ce que la couleur est jaune ?\".\n", "\n", "Cette question divise l'ensemble $S$ en deux ensembles : $S_{True}$ les valeurs qui correspondent à la couelur Jaune, et $S_{False}$ les autres.\n", "On peut alors définir le score Gini de cette partition de $S$ :\n", "\n", "$$ Gini(S_{True}, S_{False}) = \\frac{|S_{True}|}{|S|} Gini(S_{True}) + \\frac{|S_{False}|}{|S|} Gini(S_{False}), $$\n", "\n", "dont l'idée est simplement de faire une moyenne pondérée des scores Gini de chacun des sous-ensembles obtenus.\n", "\n", "Ce score mesure la qualité de la division de $S$ opérée par notre question.\n", "Si les scores Gini de $S_{True}$ et $S_{False}$ sont nuls, cela signifie que tous les éléments de $S_{True}$ ont la même valeur, et de même pour $S_{False}$.\n", "\n", "Donc, si le score Gini de $(S_{True}, S_{False})$ est nul, cela signifie que la division opérée par notre question est parfaite : tous les éléments de $S_{True}$ ont la même valeur, et tous ceux de $S_{False}$ également (mais les valeurs des deux ensembles peuvent être différentes)." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Par exemple, avec les données suivantes :\n", "\n", "| Agrume | Diamètre | Noyau | Fruit |\n", "| :------------: | :----------: | :----------: | :----------: |\n", "| False | 5 | False | Pomme\n", "| False | 5 | False | Pomme\n", "| False | 3 | False | Banane\n", "| True | 5 | False | Citron\n", "| False | 2 | True | Cerise" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Si l'on pose la question \"est-ce que le diamètre est plus grand que 5 ?\", on divise nos fruits en deux catégories :\n", "* $y_{\\ge 5} = [Pomme, Pomme, Citron]$, les fruits dont le diamètre est plus grand que $5$ ;\n", "* $y_{< 5} = [Banane, Cerise]$, les autres fruits.\n", "\n", "Et le score Gini de l'ensemble diminue. En effet, on a vu que l'ensemble complet a un score de $0.72$, mais une fois découpé en deux, le score devient :\n", "$$ Gini(y_{\\ge 5}, y_{> 5}) = \\frac{3}{5} Gini(y_{\\ge 5}) + \\frac{2}{5} Gini(y_{< 5}) = 0.46, $$\n", "\n", "et le score a donc bien baissé.\n", "\n", "Cela nous permet de différentier une \"bonne\" d'une \"mauvaise\" question : une bonne question est une question pour laquelle le score Gini diminue beaucoup. La **meilleure** question est celle qui induit la plus grande diminution de ce score." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Expériences sur les Arbres de Décision\n", "\n", "Les arbres de décision sont implémentes dans la librairie `sklearn`.\n", "La cellule de code suivant crée un arbre de décision, puis l'entraîne sur le dataset ci-dessus.\n", "\n", "La méthode `fit` permet d'entraîner un arbre de décision, où les questions posées dans chacun des sommets sont choisies comme minimisant le score Gini." ] }, { "cell_type": "code", "execution_count": null, "metadata": { "scrolled": true }, "outputs": [], "source": [ "from sklearn import tree\n", "\n", "## données\n", "# features\n", "X = [\n", " [False, 5, False],\n", " [False, 5, False],\n", " [False, 3, False],\n", " [True, 5, False],\n", " [False, 2, True],\n", "]\n", "# labels\n", "y = [\"Pomme\", \"Pomme\", \"Banane\", \"Citron\", \"Cerise\"]\n", "\n", "# arbre de décision\n", "clf = tree.DecisionTreeClassifier()\n", "\n", "# entrainement de l'arbre de décision sur le dataset (X, y)\n", "clf.fit(X, y)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "La librairie sci-kit learn (`sklearn`) implémente tout un tas d'algorithmes de machine learning.\n", "Ils fonctionnent tous de la même manière :\n", "\n", "* on crée un objet correspondant à notre modèle (`clf = tree.DecisionTreeClassifier()` ici) ;\n", "* on entraîne notre modèle sur un jeu de données avec la méthode `fit` ;\n", "* on peut prédire les labels sur de nouveaux points avec la méthode `predict`." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Vérifions que notre arbre de décision classifie correctement nos points.\n", "Pour cela, on utilise la méthode `predict` :" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "clf.predict(X)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Ce sont bien les mêmes valeurs que celles que l'on connaissait.\n", "\n", "Regardons la tête de notre arbre de décision :" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "tree.plot_tree(clf);" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Question.** À quelle classe correspond chacune des feuilles de cet arbre ? Que constatez-vous sur le score Gini ?" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Réponse :" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Performances en Test\n", "\n", "Bon, notre jeu de données est quand même un peu petit pour l'instant...\n", "\n", "Regardons ce qu'il se passe avec un jeu de données un petit peu plus compliqué :" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "from sklearn.datasets import make_moons\n", "\n", "Xmoons, ymoons = make_moons(n_samples=100, noise=0.3, random_state=42)\n", "\n", "plt.scatter(Xmoons[:, 0], Xmoons[:, 1], c=ymoons)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Question.** Entraînez un arbre de décision sur ce jeu de données, et affichez un graphe comme celui ci-dessus mais où les couleurs sont les valeurs prédites par l'arbre de décision." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "clf = tree.DecisionTreeClassifier()\n", "\n", "# entraînez le classifieur sur les données ci-dessus" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "On pourrait à première vue penser que notre classifieur est bon car il prédit les bonnes valeurs des points.\n", "Mais regardons un peu plus en détails les zonnes qui correspondent à chacune des couleurs.\n", "\n", "Sur le dessin suivant, les zones colorées en bleu sont celles où notre arbre considère que les points sont violets, et celles en vert celles où les points sont jaunes." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "xx, yy = np.meshgrid(np.arange(-2, 3, 0.1), np.arange(-2, 2, 0.01))\n", "Z = clf.predict(np.c_[xx.ravel(), yy.ravel()])\n", "Z = Z.reshape(xx.shape)\n", "plt.figure(figsize=(10,10))\n", "plt.contourf(xx, yy, Z, alpha=1, levels=1,corner_mask=False)\n", "\n", "ypred = clf.predict(Xmoons)\n", "plt.scatter(Xmoons[:, 0], Xmoons[:, 1], c=ypred)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Question.** Que pensez-vous du résultat ? Pensez-vous que les prédictions de notre arbre de décision seront toujours bonnes ?" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Réponse :" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Overfitting\n", "\n", "Le phénomène que vous observez ci-dessus s'appelle l'**overfitting** : notre classifieur apprend par coeur les données sur lesquelles il a été entraîné, ce qui rend sa précision parfaite sur les données d'entraînement, mais qui ne permet pas de faire des prédictions fiables.\n", "\n", "Pour détecter l'overfitting, on peut découper notre dataset d'entraînement en deux : une partie qui servira à entraîner notre classifieur, et une partie qui servira à vérifier s'il fait de bonnes prédictions sur des points qu'il n'a jamais vus.\n", "\n", "On parle alors de **dataset d'entraînement** et de **dataset de test**.\n", "On peut découper notre base de données $(X, y)$ en $(X_{train}, y_{train})$ et $(X_{test}, y_{test})$.\n", "La fonction `train_test_split` de `sklearn` permet de faire cela." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Commençons par générer un jeu de données de classification avec trois classes, vingt features et mille exemples." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "from sklearn.datasets import make_classification\n", "\n", "# un jeu de données de classification\n", "X, y = make_classification(n_samples=1000, n_features=20, n_classes=3,\n", " n_redundant=0, n_repeated=0, n_informative=20, \n", " random_state=42, flip_y=0.1)\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "On peut afficher notre jeu de données, pour voir à quoi il ressemble.\n", "Bien sûr, comme il y a 20 variables, on ne peut pas l'afficher comme le dataset d'au dessus...\n", "\n", "Affichons le sous la forme d'un tableau.\n", "Pour cela, on peut utiliser la librairie `pandas`.\n", "C'est une librairie très complète pour travailler avec des données, même si l'on ne va pas vraiment s'en servir ici, je vous laisse aller regarder ce qu'on peut faire avec. :)" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "scrolled": false }, "outputs": [], "source": [ "pd.DataFrame(X)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "On peut maintenant découper ce dataset en deux ensembles, un ensemble d'entraînement et un ensemble de test :" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "from sklearn.model_selection import train_test_split\n", "\n", "# on découpe notre jeu de données\n", "Xtrain, Xtest, ytrain, ytest = train_test_split(X, y, random_state=42)\n", "\n", "# on entraine un arbre de décision sur le dataset d'entrainement\n", "clf = tree.DecisionTreeClassifier()\n", "clf.fit(Xtrain, ytrain)" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "pd.DataFrame(Xtrain)" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "pd.DataFrame(Xtest)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "On voit que maintenant, notre ensemble d'entraînement contient trois quarts du dataset initial (750 points), et que l'ensemble de test contient le quart restant." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Regardons la précision de notre classifieur sur le dataset d'entraînement et sur le dataset de test :" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "print(\"Précision sur Xtrain :\", np.mean(ytrain == clf.predict(Xtrain)))\n", "print(\"Précision sur Xtest :\", np.mean(ytest == clf.predict(Xtest)))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Question.** Commentez." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Réponse :" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Une façon d'essayer d'empêcher ce phénomène d'overfitting de se produire est de limiter le nombre de questions que l'arbre peut poser sur les données, c'est à dire de limiter la profondeur maximale de l'arbre.\n", "\n", "Ainsi, il y a un équilibre à trouver :\n", "* un arbre avec une profondeur trop limitée risque de ne pas classifier correctement le jeu de données, car il ne pose pas assez de questions pour diviser correctement le jeu de données ;\n", "* un arbre avec une profondeur trop importante risque d'apprendre par coeur le jeu de données et donc de faire de moins bonnes prédictions sur des données qu'il ne connaît pas : on dit qu'il généralise mal." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Question.** On peut fixer la profondeur maximale de l'arbre de décision avec le paramètre `max_depth` de `tree.DecisionTreeClassifier`. Faites varier ce paramètre et affichez la précision sur Xtrain et sur Xtest pour chacune des valeurs de ce paramètre.\n", "\n", "Que constatez-vous ?" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# faites varier le paramètre `max_depth` de tree.DecisionTreeClassifier et observez\n", "# la précision sur les datasets d'entraînement et de test" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Réponse :" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Random Forests\n", "\n", "Comme vous venez de le constater, les arbres de décision ont une petite tendance à apprendre par coeur les données d'entraînement, et une façon de limiter cela est de limiter la profondeur de l'arbre.\n", "\n", "Une autre approche, beaucoup plus utilisée en pratique, consiste à apprendre plusieurs arbres de décision différents sur le même jeu de données, puis de combiner les résultats de tous ces arbres.\n", "Pour apprendre plusieurs arbres différents, on procède ainsi :\n", "* on tire un sous ensemble de nos données ;\n", "* on apprend un arbre de décision sur ce jeu de données,\n", "\n", "et ce, un certain nombre (fixé) de fois.\n", "\n", "Comme on apprend plusieurs arbres de décisions, on appelle le résultat (ie. l'ensemble d'arbres obtenus) une **forêt**, et comme on tire nos points au hasard, on parle de **forêt aléatoire** (random forest).\n", "\n", "Ensuite, une bonne façon de combiner ces résultats est de faire un vote : chaque arbre prédit un certain label, et notre \"forêt\" renvoie le label qui a été le plus prédit par les arbres.\n", "Cette idée s'appelle le \"bagging\" : c'est le fait de combiner des classifieurs afin de diminuer la variabilité des résultats, et donc, de limiter l'overfitting.\n", "\n", "Entraînons un tel classifieur sur nos données :" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# dans sklearn, les forêts aléatoires sont implémentées dans \"RandomForestClassifier\"\n", "from sklearn.ensemble import RandomForestClassifier\n", "\n", "# une forêt aléatoire de 100 arbres\n", "rf_clf = RandomForestClassifier(n_estimators=100)\n", "\n", "# on entraîne notre forêt sur notre dataset d'entraînement\n", "rf_clf.fit(Xtrain, ytrain)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "On peut accéder aux arbres de décision entraînés grâce à la variable `estimators_` :" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "scrolled": true }, "outputs": [], "source": [ "rf_clf.estimators_" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Question.** Affichez le premier arbre de décision." ] }, { "cell_type": "code", "execution_count": null, "metadata": { "scrolled": true }, "outputs": [], "source": [ "# affichez le premier arbre de décision (vous pouvez vous référer à une question précédente pour cela ;))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Regardons la précision des prédictions de notre forêt entraînée ainsi :" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "print(\"Précision sur Xtrain :\", np.mean(ytrain == rf_clf.predict(Xtrain)))\n", "print(\"Précision sur Xtest :\", np.mean(ytest == rf_clf.predict(Xtest)))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Question.** Que pensez-vous du résultat obtenu ? Comparez avec ceux obtenus à la question précédente." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Réponse :" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Question.** Calculez la précision moyenne des arbres de décision (stockés dans la variable `rf_clf.estimators_`). Pour cela, on itèrera sur la liste des arbres, et on calculera la précision que chaque arbre obtient.\n", "\n", "Que pensez-vous du résultat ? Est-ce la même chose que le résultat de notre forêt aléatoire ?" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "scrolled": true }, "outputs": [], "source": [ "# calculez la précision moyenne des arbres dans `rf_clf.estimators_`" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Réponse :" ] } ], "metadata": { "kernelspec": { "display_name": "Python 3", "language": "python", "name": "python3" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 3 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython3", "version": "3.8.5" } }, "nbformat": 4, "nbformat_minor": 4 }